Components of a network-connected computing infrastructure can be represented as nodes on a graph. Depending on the implementation such components can include physical components (e.g., a server or laptop), logical components (e.g., software modules or network-accessible functionality), or components representative of other attributes of the network-connected computing infrastructure. In some cases, the graph can be constructed from a Configuration Management Database (CMDB) that includes Configuration Items (CIs) representative of components of the network-connected computing infrastructure. The CIs of the CMDB can be populated, for example, by using a discovery process whereby information about the components in the network-connected computing infrastructure are collected by probes deployed through a network.